/*
 * @lc app=leetcode.cn id=1705 lang=typescript
 *
 * [1705] 吃苹果的最大数目
 */

// @lc code=start

class PQ {
  public heap: number[][] = [];

  constructor() {}

  private swap(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  private compare(i: number, j: number): number {
    return this.heap[i][0] - this.heap[j][0];
  }

  public push(val: number[]) {
    this.heap.push(val);
    this.swin(this.heap.length - 1);
  }

  public pop() {
    const ret = this.heap[0];
    this.swap(0, this.heap.length - 1);
    this.heap.pop();
    this.sink(0);
    return ret;
  }

  public peek() {
    return this.heap[0];
  }

  public isEmpty() {
    return this.heap.length === 0;
  }

  private sink(i: number) {
    while (true) {
      let child = 2 * i + 1;
      if (child >= this.heap.length) break;
      const right = child + 1;
      if (right < this.heap.length && this.compare(right, child) < 0) {
        child = right;
      }
      if (this.compare(i, child) <= 0) break;
      this.swap(i, child);
      i = child;
    }
  }

  private swin(i: number) {
    while (i > 0) {
      const parent = Math.floor(i - 1);
      if (this.compare(i, parent) >= 0) break;
      this.swap(i, parent);
      i = parent;
    }
  }
}

function eatenApples(apples: number[], days: number[]): number {
  const minPQ = new PQ();
  let n = apples.length;
  let ans = 0;
  let i = 0;
  for (; i < n; i++) {
    // 将过期的苹果移除
    while (!minPQ.isEmpty() && minPQ.peek()[0] <= i) {
      minPQ.pop();
    }
    // 将过期天数和苹果数放入优先队列
    let rottenDay = i + days[i];
    let countApple = apples[i];
    if (countApple > 0) minPQ.push([rottenDay, countApple]);
    // 当天吃1个苹果
    if (!minPQ.isEmpty()) {
      const top = minPQ.peek();
      ans++;
      top[1]--;
      if (top[1] === 0) minPQ.pop();
    }
  }

  // 将队列中的剩余苹果取出计算
  while (!minPQ.isEmpty()) {
    // 将过期的苹果移除
    while (!minPQ.isEmpty() && minPQ.peek()[0] <= i) {
      minPQ.pop();
    }

    if (minPQ.isEmpty()) break;
    // 计算队列中能吃的苹果数
    const top = minPQ.pop();
    const count = Math.min(top[0] - i, top[1]);
    ans += count;
    i += count;
  }

  return ans;
}
// @lc code=end
